package src.CodeTop;

/**
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 *
 *  
 *
 * 示例 1：
 *
 *
 * 输入：head = [1,2,2,1]
 * 输出：true
 * 示例 2：
 *
 *
 * 输入：head = [1,2]
 * 输出：false
 *
 * 用队列实现栈的核心在于让插入队列的新元素在队首,这样出队列的时候就是后进先出,要做到这样的话,就需要将之前的元素出队列后重新进队列
 *
 */

public class _234PalindromeLinkedList {
    public static void main(String[] args) {
        int[] nums = {1, 2, 2, 1};
        ListNode head = TestListNode.generateLinkedList(4, nums);
        boolean b = isPalindrome1(head);
        System.out.println(b);
    }

    // 取出数值存储再反转
    public static boolean isPalindrome(ListNode head) {
        // 校验合法性
        if (head == null)
            return false;
        if (head.next == null)
            return true;
        // 定义字符缓冲流
        StringBuilder sb = new StringBuilder();
        // 定义遍历指针
        ListNode cur = head;
        // 遍历链表
        while (cur != null) {
            sb.append(cur.val);
            cur = cur.next;
        }
        String originalStr = sb.toString();
        String alterStr = sb.reverse().toString();
        return originalStr.equals(alterStr);
    }

    // 快慢指针法反转链表法
    public static boolean isPalindrome1(ListNode head) {
        // 校验合法性
        if (head == null || head.next == null) {
            return true;
        }
        // 定义快慢指针
        ListNode slow = head, fast = head;
        // 遍历链表
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 反转后半部分
        slow.next = reverse(slow.next);
        TestListNode.showLinkedList(slow);
        // 定义双遍历指针
        ListNode cur1 = head, cur2 = slow.next;
        // 同时遍历链表
        while (cur2 != null) {
            if (cur1.val != cur2.val) {
                return false;
            }
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return true;
    }
    public static ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode tail = head.next;
        ListNode p = reverse(head.next);
        head.next = tail.next;
        tail.next = head;
        return p;
    }

    // 栈存值法
}
